package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/11/12 09:34
 **/
public class Day68_1_Num790_NumTilings {
    class Solution {
        int mod = (int)1e9 + 7;
        int[][] matrix = {{0,1,1,1}, {0,0,1,1}, {0,1,0,1}, {1,0,0,1}};
        public int numTilings(int n) {
            long ans[][] = new long[n][4];
            ans[0] = new long[]{1,0,0,1};
            for(int i = 1; i < n; ++i){
                for(int j = 0; j < 4; ++j){
                    for(int k = 0; k < 4; ++k)
                        ans[i][j] += ans[i-1][k] * matrix[k][j];
                    ans[i][j] %= mod;
                }
            }
            return (int)ans[n-1][3];
        }
    }
}